#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
# http://www.careercup.com/question?id=14875685
#Given a matrix with 1's and 0's, find the number of groups of 1's. A group is defined by horiz/vertically adjacent 1's.

import os, re, sys, getopt
import logging
import locale
from utils import *
import copy

def reset(m, i, j):
    if not m[i][j]: return
    m[i][j] = 0
    if i > 0: reset(m, i - 1, j)
    if i < len(m) - 1: reset(m, i + 1, j)
    if j > 0: reset(m, i, j - 1)
    if j < len(m[0]) - 1: reset(m, i, j + 1)

@time_profile
def find_num_groups_david(m):
    m = copy.deepcopy(m)
    count = 0
    if not m or not m[0]: return 0
    rows, cols = len(m), len(m[0])
    for i in range(0, rows):
        for j in range(0, cols):
            if m[i][j]:
                reset(m, i, j)
                count += 1
    return count

#incorrect!
@time_profile
def find_num_groups_lobatt(om):
    m = copy.deepcopy(om)
    for i in range(0, len(m)):
        for j in range(0, len(m[0])):
            if j + 1 < len(m[0]) and m[i][j+1] == 1: m[i][j] = 0;
            if i + 1 < len(m) and m[i + 1][j] == 1: m[i][j] = 0;
    num = 0;
    for a in m:
        num += sum(a)
    #print "after shrink:"
    #print_matrix(m)
    return num

def print_matrix(m):
    for a in m: print a

if __name__ == '__main__':
    N = 5
    m = []
    for i in range(0,N):
        m.append(random_arr(5,0,1))
    print_matrix(m)
    print find_num_groups_david(m)
    print find_num_groups_lobatt(m)
